updated: 2022-01-23_12:32:30-05:00


Theorem: The class of regular languages is closed under complementation

Proof:

Let A be a regular language
Let M be the DFA that accepts A
Let M' be the result of switching the accepting states of every state in M

if M=(Q,Σ,δ,q0,f)M=(Q,\Sigma,\delta,q_0,f) then
M=(Q,Σ,δ,q0,Qf)M'=(Q,\Sigma,\delta,q_0,Q-f) then
we claim L(M)=AL(M')=\overline{A}

how do we prove this?

Suppose wAw\in A then ww lead to an accepting state in MM
ww leads to the same state in MM' but that is not an accepting state in MM'

if wAw\in A then MM accepts it
if w∉Aw\not\in A then MM' accepts it
L(M)=A\therefore L(M')=\overline A